package 算法.LeetCode91.每日打卡题目;

import 算法.NiuKe.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author: 谢君臣
 * @create: 2021-02-15 15:37
 * @founction: XXXX
 */
public class day15 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(5);
        System.out.println(sumNumbers(root));
    }
    public static int sumNumbers(TreeNode root) {
        Integer sum = 0;
        if (root==null)
            return sum;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node!=null){
            stack.push(node);
            if (node.left!=null)
                node.left.val += node.val*10;
            node = node.left;
        }
        boolean falg = true;
        while (!stack.empty()){
            TreeNode n = stack.pop();
            if (falg&&n.left==null&&n.right==null){
                sum = sum + n.val;
                falg = false;
            }
            if (n.right!=null){
                falg = true;
                n.right.val += n.val*10;
                node = n.right;
                while (node!=null){
                    stack.push(node);
                    if (node.left!=null)
                        node.left.val += node.val*10;
                    node = node.left;
                }
            }
        }
        return sum;
    }
    public int sumNumbers1(TreeNode root) {
        Integer sum = 0;
        if (root==null)
            return sum;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (isLeaf(node)) {
                sum = sum + node.val;
            }else {
                if (node.left!=null){
                    node.left.val = node.val*10 + node.left.val;
                    queue.add(node.left);
                }
                if (node.right!=null){
                    node.right.val = node.val*10 + node.right.val;
                    queue.add(node.right);
                }
            }
        }
        return sum;
    }
    public boolean isLeaf(TreeNode node){
       return node.left ==null&&node.right==null;
    }

}
